A B D B E F E G A C
1 2 3 2 3 4 3 4 1 2

          A          1
         / \        / \
        B   C      2   7
       / \        / \ 
      D   E      3   4
         / \        / \
        F   G      5   6

int tot,head[N],ver[2*N],R[2*N],first[N],dir[N];  
//ver:节点编号 R：深度 first：点编号第一次位置 dir：距离  
void dfs(int u ,int dep) {  
    vis[u] = true;   
    ver[++tot] = u;  
    first[u] = tot;  
    R[tot] = dep;  
    for(int k=head[u]; k!=-1; k=e[k].next)  
        if( !vis[e[k].v] ) {  
            int v = e[k].v , w = e[k].w;  
            dir[v] = dir[u] + w;  
            dfs(v,dep+1);  
            //下面两句表示dfs的时候还要回溯到上面  
            ver[++tot] = u;   
            R[tot] = dep;  
        }  
}

void ST(int n) {  
    for(int i=1;i<=n;i++)  
        dp[i][0] = i;  
    for(int j=1;(1<<j)<=n;j++) {  
        for(int i=1;i+(1<<j)-1<=n;i++) {  
            int a = dp[i][j-1] , b = dp[i+(1<<(j-1))][j-1];  
            dp[i][j] = R[a]<R[b]?a:b;  
        }  
    }  
}  
//中间部分是交叉的。  
int RMQ(int l,int r) {  
    int k=0;  
    while((1<<(k+1))<=r-l+1)  
        k++;  
    int a = dp[l][k], b = dp[r-(1<<k)+1][k]; //保存的是编号  
    return R[a]<R[b]?a:b;  
}  
  
int LCA(int u ,int v) {
    int x = first[u] , y = first[v];  
    if(x > y) swap(x,y);  
    int res = RMQ(x,y);  
    return ver[res];  
}  
